package Learn;

import java.util.ArrayList;
import java.util.Arrays;

public class Find {
    public static void main(String[] args) {

        //查找数组中的元素返回下标（重复）
//        int[] arr = {12, 14, 12, 15, 17, 45, 12, 86, 143};
//        int[] newArr = Find(arr, 12);
//        int i = 0;
//        while (newArr[i] != -1) {
//            System.out.println(newArr[i]);
//            i++;
//        }

        //二分查找 min max表示范围 mid中间
//        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
//        int i = MidFind(arr, 80);
//        System.out.println(i);


    }

    //插值查找
    //数组元素分布比较均匀可以使用
    //mid=min+(key-arr[min])/(arr[max]-arr[min])*(max-min)

    //斐波那契查找
    //mid=min+黄金分割点左半边长度-1


    //二分
    public static int MidFind(int[] arr, int key) {
        int min = 0;
        int max = arr.length - 1;
        while (min <= max) {
            int mid = (min + max) / 2;
            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] < key) {
                min = mid + 1;
            } else if (arr[mid] > key) {
                max = mid - 1;
            }
        }
        return -1;
    }

    //基本查找
    public static int[] Find(int[] arr, int key) {
        //ArrayList<Integer> list=new ArrayList<>();

        int[] newArr = new int[arr.length];

        Arrays.fill(newArr, -1);
//        for (int i = 0; i < newArr.length; i++) {
//            newArr[i] = -1;
//        }
        int j = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {
                newArr[j] = i;
                j++;
            }
        }
        return newArr;
    }

}
